Список всех заданий

За эти я буду ставить очень мало баллов.

• возведение в степень
• возведение в степень за логарифмическое время
• алгоритм Евклида
• извлечение корня методом Ньютона
• рекурсивное вычисление синуса из соотношения

Эти задачи я с удовольствием приму от тех, кто их мне еще не сдавал

• вывести все правильные скобочные последовательности длины n
• вывести все двоичные числа длины не более n, в которых нет двух идущих подряд единиц
• дана строка, вывести все “слова”, которые можно получить из букв этой строки
• то же самое, но вернуть в виде List-а
• множество уникальных элементов задано строкой, вывести все подмножества
• вернуть все подмножества в виде List-а
• Треугольник Паскаля: вывести i,j-й элемент, вывести весь треугольник, вывести треугольник, повернутый на бок

Эти задачи я приму с особенно большим удовольствием

• написать программу, которая выводит все способы набрать нужную сумму с помощью российских монет и купюр (8 рублей = 5 + 2 + 1 = 5 + 1 + 1 + 1=2+2+2+2=...)
• расставить на доске NxN N ферзей так, чтобы они не били друг друга
• обойти доску NxN ходом коня или вывести, что это не возможно
• поиск кратчайшего пути в лабиринте, заданном в виде двумерного массива
• QuickSort на массивах
• QuickSort на List-ах
• Реализовать двусвязный список. Каждый элемент списка хранит целое число и ссылки на предыдущий и следующий элементы (или null, если какой-то ссылки нет). Целое число задается в конструкторе и остается неизменным, а ссылки надо уметь менять. Элемент должен уметь предоставлять информацию о своем целочисленном значении и ссылки на предыдущий и следующий.
• MergeSort (сортировка слиянием)
• Двоичное дерево поиска: добавление, поиск элемента, вывод на экран
• Двоичное дерево поиска: удаление
• Двоичное дерево поиска: подсчет количества вершин, подсчет листьев, вершин с одним сыном, вершин с двумя детьми, подсчет высоты, поиск максимума/минимума (здесь можно делать не все, а то, что больше нравится)
• АВЛ-деревья: балансировка
• АВЛ-деревья, построение дерева за N log(N)

• Вывести максимальную возрастающую подпоследовательность из массива чисел (2 балла)
• Вывести максимальную общую подпоследовательность двух массивов (3 балла)
• Дана матрица NxN неотрицательных чисел. По матрице можно двигаться, причем только в сторону увеличения координаты y (номер строки) и изменяя x не более, чем на 1. Найти путь из ячейки в верхней строке на нижнюю строку, причем такой, что сумма элементов в этом пути (включая первый и последний) максимальна. (3 балла)
• дано положительное число X, сколькими способами можно представить число X в виде суммы элементов данного массива (элементы массива – положительные числа), где каждый элемент берется не больше одного раза? (3 балла)
• Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца (2 балла).
• Железная дорога с односторонним движением имеет n станций. Известны цены билетов от i-ой станции до j-ой (при i < j - в обратную сторонону проезда нет). Найти минимальную стоимость проезда от начала до конца (с учетом возможной экономии за счет пересадок) (3 балла).
• Дана квадратная таблица a[1..n][1..n] и число m⇐n. Для каждого квадрата размера m на m в этой таблице вычислить сумму стоящих в нем чисел. Общее число действий должно быть порядка n*n. (4 балла)

• Обход в глубину с неявным стеком (2 балла)
• Обход в глубину с явным стеком (2 балла)
• Обход в ширину (2 балла)
• Топологическая сортировка (3 балла)
• Поиск кратчайшего пути во взвешенном графе алгоритмом Беллмана-Форда (4 балла), демонстрация работы на интересном примере из жизни +1 балл
• Поиск кратчайшего пути во взвешенном графе алгоритмом Дейкстры (5 баллов), демонстрация работы на интересном примере из жизни +1 балл
• Поиск всех кратчайших путей во взвешенном графе алгоритмом Флойда-Уоршолла (5 баллов), демонстрация работы на интересном примере из жизни +1 балл

По желанию баллы за эти задачи могут ставиться в 4 модуль

• Вечеринка в фирме (3 балла). Фирма имеет иерархическую структуру в виде дерева, в корне которого директор. У каждого сотрудника есть ранг - некоторое число. Чтобы всем было весело, директор распорядился, чтобы никто не оказался на вечеринке со своим непосредственным начальником. 1. Разработайте алгоритм, выдающий список приглашенных с максимальным суммарным рейтингом. 2. (+1 балл) То же самое, но директор обязательно должен быть приглашен.
• Триангуляция (4 балла). Дан выпуклый многоугольник, разбить его на треугольники так, чтобы суммарная длина разрезов была минимальной.

• Вывести сильно связные компоненты графа (4 балла первому приславшему, 3 всем остальным)
• Алгоритм Прима (3-5 баллов в зависимости от качества реализации)
• Реализовать алгоритм Эдмондса-Карпа (метод Форда-Фалкерсона с выбором дополняющего пути поиском в ширину) 5 баллов
• Электрическая цепь представляет собой граф. Все ребра графа имеют какое-то сопротивление. Написать программу, которая вычисляет сопротивление между первой и последней вершинами (6 баллов)

• Дана строка, создать список листьев дерева Хаффмана, то есть список, в каждом элементе которого хранится буква и сколько раз она встречается (1 балл)
• Из списка листьев из предыдущей задачи построить дерево Хаффмана (4 балла)
• По построенному в предыдущей задаче дереву зашифровать исходную строку и вывести результат в виде строки нулей и единиц (4 балла)
• Используя дерево раскодировать строку (4 балла)
• Используя результаты всех предыдущих задач архиватор/разархиватор (6 баллов)